package day0116

import (
	"fmt"
	"math"
)

func minWindow(s string, t string) string {
	window, need := make(map[byte]int), make(map[byte]int)
	for i := 0; i < len(t); i++ {
		need[t[i]]++
	}
	left, right := 0, 0
	valid := 0
	rLeft, rRight := 0, math.MaxInt64
	for right < len(s) {
		c := s[right]
		right++
		if _, ok := need[c]; ok {
			window[c]++
			if window[c] == need[c] {
				valid++
			}
		}
		for valid == len(need) {
			if right-left < rRight-rLeft {
				rLeft = left
				rRight = right
			}
			t := s[left]
			left++
			if _, ok := need[t]; ok {
				if window[t] == need[t] {
					valid--
				}
				window[t]--
			}
		}
	}
	fmt.Println(rLeft, rRight)
	if rRight == math.MaxInt64 {
		return ""
	}
	return s[rLeft:rRight]
}
